﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution42
{
    public int Trap2(int[] height)
    {
        int len=height.Length;
        int[] leftH=new int[len];
        int[] rightH=new int[len];
        int max =0;

        for (int i = 0; i < len; i++) {

            
            leftH[i] = max;

            max = Math.Max(max, height[i]);
        }
        max=0;
        for (int i = len-1; i >=0; i--)
        {


            rightH[i] = max;

            max = Math.Max(max, height[i]);
        }
        int sum = 0;
        for (int i = 0; i < len; i++)
        {


           
            int curWater=Math.Min(leftH[i], rightH[i])- height[i];
            if(curWater < 0)
            {
                curWater = 0;
            }
            Console.WriteLine(i + "  water " + curWater);
            sum += curWater;
        }
        return sum;
    }
    //双指针法
    public int Trap(int[] height)
    { 

        int len=height.Length;
        int left = 0;
        int right= len-1;
        int leftMax = height[left];
        int rightMax = height[right];
        int sum = 0;

        while (left < right) { 
        
        if(leftMax < rightMax)  { 
                
                
                sum += leftMax- height[left];
                
                left++;
                leftMax=Math.Max(leftMax, height[left]);

            }
            else
            {
                sum += rightMax - height[right];

                right--;
                rightMax = Math.Max(rightMax, height[right]);
            }

            Console.WriteLine(sum);
        }
        return sum;


    
    
    }
    }
class Program42
{

    static void Main42(string[] args)
    {

        Solution42 solution = new Solution42();

        int[] height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
     int res=   solution.Trap(height);
        Console.WriteLine(res);

    }
}
